package fun.coding.leetcode;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

public class BinaryTreePreorderTraversal {

	public static void main(String[] args) {
		BinaryTreePreorderTraversal btpret = new BinaryTreePreorderTraversal();
		
		/*      1
		 *    2   3
		 *  4   5
		 *  pre order-> 1 2 4 5 3  
		 */
		TreeNode root = new TreeNode(1);
		root.left = new TreeNode(2);
		root.right = new TreeNode(3);
		root.left.left = new TreeNode(4);
		root.left.right = new TreeNode(5);
		
		List<Integer> res = btpret.preorderTraversal(root);
		
		for (int i : res) {
			System.out.println(i);
		}

	}
	
	public List<Integer> preorderTraversal(TreeNode root) {
		Stack<TreeNode> stack = new Stack<TreeNode>();
		List<Integer> res = new LinkedList<Integer>();
		
		if (root == null) return res;
		// an extra pointer
		TreeNode cur = root;
		while (!stack.isEmpty() || cur != null) {
			if (cur != null) {
				stack.push(cur);
				res.add(cur.val);
				cur = cur.left;
			} else {
				TreeNode t = stack.pop();
				cur = t.right;
			}
		}
		return res;
	}

}
